﻿//BC138 矩阵转置
//https://www.nowcoder.com/practice/351b3d03e410496ab5a407b7ca3fd841?tpId=290&tqId=39926&ru=/exam/oj
//#include <iostream>
//
//using namespace std;
//
//const int N = 15;
//
//int n, m;
//int a[N][N];
//
//int main()
//{
//	cin >> n >> m;
//
//	for (int i = 0; i < n; i++)
//		for (int j = 0; j < m; j++)
//			cin >> a[i][j];
//
//	for(int i = 0; i< m; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			cout << a[j][i] << " ";
//		}
//
//		cout << endl;
//	}
//		
//	return 0;
//}


//四个选项
// https://ac.nowcoder.com/acm/problem/202493
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//int ret;
//int cnt[5]; 
//int m, x, y;
//bool same[13][13]; 
//vector<int> path; 
//
//bool isSame(int pos, int x)
//{
//	for (int i = 1; i < pos; i++)
//	{
//		if (same[pos][i] && path[i] != x) return false;
//	}
//	return true;
//}
//
//void dfs(int pos)
//{
//	if (pos > 12)
//	{
//		ret++;
//		return;
//	}
//	for (int i = 1; i <= 4; i++)
//	{
//		if (cnt[i] == 0) continue; // 没有使⽤次数
//		if (!isSame(pos, i)) continue; // 需要相同的位置，没有相同
//		cnt[i]--;
//		path.push_back(i);
//		dfs(pos + 1);
//		path.pop_back();
//		cnt[i]++;
//	}
//}
//int main()
//{
//	for (int i = 1; i <= 4; i++) cin >> cnt[i];
//	cin >> m;
//	while (m--)
//	{
//		cin >> x >> y;
//		same[x][y] = same[y][x] = true;
//	}
//	path.push_back(0); // 先放进去⼀个占位符
//	dfs(1);
//	cout << ret << endl;
//	return 0;
//}

//42. 接雨水
//https://leetcode.cn/problems/trapping-rain-water/submissions/633353701/
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//class Solution
//{
//public:
//	int trap(vector<int>& height)
//	{
//		int n = height.size();
//		if(n == 0) 
//		{
//			return 0;
//		}
//
//		vector<int> left(n);
//		vector<int> right(n);
//
//		left[0] = height[0];
//		for (int i = 1; i < n; i++) left[i] = max(left[i - 1], height[i]);
//
//		right[n - 1] = height[n - 1];
//
//		for (int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], height[i]);
//
//		int ret = 0;
//		for (int i = 1; i < n - 1; i++)
//		{
//			ret += min(left[i], right[i]) - height[i];
//		}
//		return ret;
//	}
//};


//疯狂的自我检索者
//https://ac.nowcoder.com/acm/problem/205826

//#include <iostream>
//
//using namespace std;
//
//const int N = 2e5 + 10;
//
//int n, m;
//int a[N];
//
//int main()
//{
//	cin >> n >> m;
//	int ret1 = 0;
//	int ret2 = 0;
//
//	for (int i = 0; i < n - m; i++)
//	{
//		cin >> a[i];
//		ret1 += a[i];
//		ret2 += a[i];
//	}
//	
//	for (int i = 1; i <= m; i++)
//	{
//		ret1 += 1;
//		ret2 += 5;
//	}
//
//	double x1 = (double)ret1 / n;
//	double x2 = (double)ret2 / n;
//
//	printf("%.5f %.5f\n", x1, x2);
//
//	return 0;
//}

// 栈和排序
// https://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f?tpId=196&tqId=37173&ru=/exam/oj
//#include <iostream>
//#include <stack>
//#include <vector>
//
//using namespace std;
//
//class Solution
//{
//    bool hash1[50005] = { 0 };
//public:
//    vector<int> solve(vector<int>& a)
//    {
//        stack<int> st;
//        int n = a.size();
//        
//        int mark = n;
//        vector<int> ret;
//
//        for (auto& e : a)
//        {
//           st.push(e);
//           hash1[e] = true;
//
//           while (hash1[mark])
//           {
//               mark--;
//           }
//
//           if (st.size() > 0 && a[mark] >= mark)
//           {
//               ret.push_back(st.top());
//               st.pop();
//           }
//        }
//
//        return ret;
//    }
//};


//加减
//https://ac.nowcoder.com/acm/problem/224938
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//typedef long long LL;
//const int N = 1e5 + 10;
//
//LL n, k;
//LL arr[N];
//LL sum[N]; // 前缀和数组
//
//LL cal(int l, int r)
//{
//	int mid = (l + r) / 2;
//	return (mid - l - r + mid) * arr[mid] - (sum[mid - 1] - sum[l - 1]) +
//		(sum[r] - sum[mid]);
//}
//
//int main()
//{
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//
//	sort(arr + 1, arr + 1 + n);
//
//	// 初始化前缀和数组
//	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i];
//
//	int left = 1, right = 1, ret = 1;
//	while (right <= n)
//	{
//		// 进窗口
//		LL cost = cal(left, right);
//		while (cost > k) // 判断
//		{
//			left++; // 出窗口
//			cost = cal(left, right);
//		}
//		// 更新结果
//		ret = max(ret, right - left + 1);
//		right++;
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}